package generator.statistics;

import generator.equation.*;
import generator.filedeal.ReadFileDeal;
import generator.structure.Pair;

import java.io.*;
import java.util.*;

import org.apache.commons.math3.stat.inference.ChiSquareTest;

public final class GetTwoSets {

	Set<Pair<Integer, Integer>> combinedData = new HashSet<Pair<Integer, Integer>>();
	Set<Pair<Integer, Integer>> mutualInfo = new HashSet<Pair<Integer, Integer>>();
	Map<Pair<String, String>, Integer> jointDistr = new HashMap<Pair<String, String>, Integer>();
	HashMap<String, Integer> firstMargiDistr = new HashMap<String, Integer>();
	HashMap<String, Integer> secondMargiDistr = new HashMap<String, Integer>();
	Map<Pair<Integer, Integer>, HashMap<Pair<String, String>, Integer>> mutualInfoDistri = new HashMap<Pair<Integer, Integer>, HashMap<Pair<String, String>, Integer>>();

	private long Rows; 

	public static final double seita = 0.85;

	int[] numericalS;
	
	int cols; 

	HashMap<Integer, Integer> colDistiNum = new HashMap<Integer, Integer>(); 
	Map<Integer, HashMap<String, Integer>> colValTime = new HashMap<Integer, HashMap<String, Integer>>(); 

	NumericalSet numericalSet;
	
	Set<Integer> candidate = new HashSet<Integer>();
	Set<Integer> uncandidate = new HashSet<Integer>();
	
	ReadFileDeal fileReader;
	
	//used to record every nodes' bian
	HashMap<Integer,ArrayList<Integer>> recordEquation = new HashMap<Integer,ArrayList<Integer>>();
			
	//each bian's weight
	ArrayList<Pair<Pair<Integer, Integer>, Double>> edgeInfoList = new ArrayList<Pair<Pair<Integer, Integer>, Double>>();
	
	int numericalPartition;
	
	//which group and its distinct so that keep the distinct under some value
	ArrayList<Pair<Set<Integer>, Integer>> groupInfo = new  ArrayList<Pair<Set<Integer>, Integer>>();
	int upperLimit = 1000000000;
	int numInGroup = 4;
	int filter;
	double threshold;
	
	int allRelation;
	int keptRelation;
	
	public GetTwoSets(ReadFileDeal fileReader, int[] numericalS, int numericalPartition, 
			int filter, int upperLimit, double threshold, int numInGroup) {
		this.fileReader = fileReader;
		this.numericalS = numericalS;
		this.numericalPartition = numericalPartition;
		
		NumericalSet numericalSet = new NumericalSet(numericalPartition);
		fileReader.setNumericalClass(numericalSet);
		
		this.filter = filter;
		this.upperLimit = upperLimit;
		this.threshold = threshold;
		this.numInGroup = numInGroup;
	}

	public HashMap<Integer, Integer> getDistiNum() {

		Map<Integer, Set<String>> colDistiVal = fileReader.readData();
		Set<Integer> keys = colDistiVal.keySet(); 
		// System.out.println("getDistiNum: " + colDistiVal);
		for (Iterator<Integer> it = keys.iterator(); it.hasNext();) { 
			int colNum = it.next();
			colDistiNum.put(colNum, colDistiVal.get(colNum).size());
		}

		for(int i = 0; i < numericalS.length; i++) {
			colDistiNum.put(numericalS[i], numericalPartition);
		}
		
		return colDistiNum;
	}

	// /////////////////////////////////////////////////////////////////
	public void roughClassify() {

		HashMap<Integer, Integer> dn = getDistiNum();
		// System.out.println("getCandidate: " + dn);
		Set<Integer> colNum = dn.keySet();

		for (Iterator<Integer> it = colNum.iterator(); it.hasNext();) {
			int col = it.next();
			if (((double) dn.get(col)) > 0) {
				candidate.add(col);
			} else {
				uncandidate.add(col);
			}
		}

	}

	// numerical
	public void roughClassify2() {

		HashMap<Integer, Integer> dn = getDistiNum();
		// System.out.println("getCandidate: " + dn);
		Set<Integer> colNum = dn.keySet();

		for (Iterator<Integer> it = colNum.iterator(); it.hasNext();) {
			int col = it.next();
			if (((double) dn.get(col)) > filter) {
				candidate.add(col);
			} else {
				uncandidate.add(col);
			}
		}

		for (int i = 0; i < numericalS.length; i++) {
			candidate.add(numericalS[i]);
		}

	}

	//////////////////////////////////////////////////////////////////////////////////////

	// [12 13 14],<12,13> <12,14> <13,14>
	public void genTwoSets() {
		
		roughClassify2();

		Integer[] priData = new Integer[candidate.size()];
		candidate.toArray(priData);

		String temp = "";
		for(int i = 0; i < priData.length; i++) {
			temp += priData[i] + " ";
		}
		
		System.out.println("pridata: " + temp);
		
		//used to record every nodes' bian
		HashMap<Integer,ArrayList<Integer>> recordEquation = new HashMap<Integer,ArrayList<Integer>>();
		
		//each bian's weight
		ArrayList<Pair<Pair<Integer, Integer>, Double>> edgeInfoList = new ArrayList<Pair<Pair<Integer, Integer>, Double>>();
		
		for (int i = 0; i < priData.length - 1; i++) {
			
			Integer x = priData[i];
			
			for (int j = i + 1; j < priData.length; j++) {

				Integer y = priData[j];
				
				Pair<Integer, Integer> tempPair = new Pair<Integer, Integer>(x, y);

				fileReader.readData(x, y);
			
				jointDistr = fileReader.getJointDistr();
				firstMargiDistr = fileReader.getFirstMargiDistr();
				secondMargiDistr = fileReader.getSecondMargiDistr();
				
				//System.out.println("first: " + x + " second: " + y);
				
				double result = 0;
				
				Set<Pair<String, String>> keys = jointDistr.keySet();
								
				Set<String> keyFX = firstMargiDistr.keySet();
				Set<String> keyFY = secondMargiDistr.keySet();
				
				long[][] contingency = new long[keyFX.size()][keyFY.size()];
				System.out.println("first: " + x + "---" + keyFX.size() + " second: " + y + "---" + keyFY.size());
				
				//System.out.println(firstMargiDistr);
				//System.out.println(secondMargiDistr);
				
				int m = 0; 
				for (Iterator<String> ite1 = keyFX.iterator(); ite1.hasNext();) {
					
					String valueX = ite1.next();
								
					int n = 0; 
					for (Iterator<String> ite2 = keyFY.iterator(); ite2.hasNext();) {
						
						int join = 0;
						String valueY = ite2.next();
					
						Pair<String, String> valueXY = new Pair<String, String>(valueX, valueY);

						if (jointDistr.get(valueXY) == null)
							join = 0;
						else
							join = jointDistr.get(valueXY);

						contingency[m][n] = join;
						
//						meanSquare MS = new meanSquare((double)firstMargiDistr.get(valueX)/30000, (double)secondMargiDistr.get(valueY)/30000, (double)join/30000);
						meanSquare MS = new meanSquare((double)firstMargiDistr.get(valueX), (double)secondMargiDistr.get(valueY), (double)join);
						
						result += MS.getResult();
						// System.out.println("acumresult: " + result);
						n++;
					}
					m++;
				}

				ChiSquareTest cst = new ChiSquareTest();
				double p_value = cst.chiSquareTest(contingency);
				result = p_value;
				
				System.out.println("p-value: " + p_value);
				
				// store the correlation for each node
				if(result <= threshold) {
					
					allRelation++;
					
					//store the edge weight
					Pair<Integer, Integer> edge = new Pair<Integer, Integer>();
					if(x <= y) 
						edge = new Pair<Integer, Integer>(x, y);
					else
						edge = new Pair<Integer, Integer>(y, x);
					
					Pair<Pair<Integer, Integer>, Double> edgeInfo = new Pair<Pair<Integer, Integer>, Double>(edge, result);
					edgeInfoList.add(edgeInfo);
//					System.out.println(edgeInfoList);
					
					//begin to keep the information of each node
					Integer startNodeRecord = y;
					Integer endNodeRecord = x;
					
					if(recordEquation.get(x) == null){
						
						ArrayList<Integer> pairArray = new ArrayList<Integer>();
						pairArray.add(startNodeRecord);
						recordEquation.put(x, pairArray);
						
					} else {
						
						ArrayList<Integer> pairArray = recordEquation.get(x);
						pairArray.add(startNodeRecord);
						recordEquation.put(x, pairArray);
						
					}
					
					if(recordEquation.get(y) == null){
						
						ArrayList<Integer> pairArray = new ArrayList<Integer>();
						pairArray.add(endNodeRecord);
						recordEquation.put(y, pairArray);
						
					} else {
						
						ArrayList<Integer> pairArray = recordEquation.get(y);
						pairArray.add(endNodeRecord);
						recordEquation.put(y, pairArray);
						
					}
					
				}
			}
			
			if(recordEquation.get(x) == null) uncandidate.add(x);
			
		}

		this.recordEquation = recordEquation;
		this.edgeInfoList = edgeInfoList;
		
		//get the two largest correlated edges
		keepTwoLargest(recordEquation, edgeInfoList);
		
		setCombineDataSet();
	}
	
	
	
	private void keepTwoLargest(HashMap<Integer,ArrayList<Integer>> recordEquation, 
			ArrayList<Pair<Pair<Integer, Integer>, Double>> edgeInfoList) {
		
		//after the weight computation, begin to sort the weight
		HashMap<Pair<Integer, Integer>, Integer> edgePosition = new HashMap<Pair<Integer, Integer>, Integer>();
		
		edgeInfoList = sort(edgeInfoList);
		int edgeLength = edgeInfoList.size();
		
		int[] edgeFlag = new int[edgeLength];
		
		//record the position in the edgeInfoList in order to delete the edge
		for(int i = 0; i < edgeLength; i++) {
			Pair<Integer, Integer> columnPair = edgeInfoList.get(i).first_;
			int position = i;
			edgePosition.put(columnPair, position);
		}
		
		//keep the largest two edge
		Set<Integer> columnSet = recordEquation.keySet(); //all bian
		HashMap<Integer, ArrayList<Integer>> columnInfo = new HashMap<Integer, ArrayList<Integer>>();
		
		//how many edges every column has  so far and this is the initial
		for(Iterator<Integer> ite = columnSet.iterator(); ite.hasNext();) {
			
			int column = ite.next();
			ArrayList<Integer> al = new ArrayList<Integer>();
			columnInfo.put(column, al);
		}
		
		//begin to draw the line
		for(int i = 0; i < edgeLength; i++) {
			
			if(edgeFlag[i] == 1) continue;
			
			edgeFlag[i] = 1; //flag the current edge
			
			ArrayList<Integer> currentNeighbourList = new ArrayList<Integer>();
			
			Pair<Integer, Integer> columnPair = edgeInfoList.get(i).first_;
			int column1 = columnPair.first_;
			int column2 = columnPair.second_;
			
			if(colDistiNum.get(column1) >= upperLimit) {
				edgeFlag = drop(column1, edgePosition, currentNeighbourList, edgeFlag);
				uncandidate.add(column1);
				
				if(colDistiNum.get(column2) >= upperLimit) {
					edgeFlag = drop(column2, edgePosition, currentNeighbourList, edgeFlag);
					uncandidate.add(column2);
				}
				
				continue;
			}
			
			//if drop this edge, delete in recordEquation
			if(!whetherAdd(columnPair, columnInfo, groupInfo)) {
				ArrayList<Integer> deleteList = new ArrayList<Integer>();
				deleteList.add(column2);
				recordEquation = delete(recordEquation, deleteList, column1);
				continue;
			}
			
			//column1----------------
			
			currentNeighbourList = columnInfo.get(column1);
			currentNeighbourList.add(column2);
			
			//drop off column1' other edges and delete in edgeInfoList
			if(currentNeighbourList.size() == 2 && recordEquation.get(column1).size() > 2) {
				edgeFlag = drop(column1, edgePosition, currentNeighbourList, edgeFlag);
			}
				
			//column2------------------
			
			currentNeighbourList = columnInfo.get(column2);
			currentNeighbourList.add(column1);
			
			//drop off column2' other edges and delete in edgeInfoList
			if(currentNeighbourList.size() == 2 && recordEquation.get(column2).size() > 2) {
				edgeFlag = drop(column2, edgePosition, currentNeighbourList, edgeFlag);
			}
				
		}
	}
	
	/**
	 * 
	 * @param columnPair
	 * @param columnInfo
	 * @param groupInfo
	 * @return true--keep columnPair, false--drop the columnPair
	 */
	private boolean whetherAdd(Pair<Integer, Integer> columnPair,
			HashMap<Integer, ArrayList<Integer>> columnInfo,
			ArrayList<Pair<Set<Integer>, Integer>> groupInfo) {

		boolean whether;
		
		int column1 = columnPair.first_;
		int column2 = columnPair.second_;
		
		int currentGroupNumber = groupInfo.size();
		
		int flag1 = 0;
		int flag2 = 0;
		
		int whichGroup1 = 0;
		int whichGroup2 = 0;
		
		for(int i = 0; i < currentGroupNumber; i++) {
			
			Set<Integer> oneGroup = groupInfo.get(i).first_;
			int workload = groupInfo.get(i).second_;
			
			if(oneGroup.contains(column1)) {
				flag1 = 1;
				whichGroup1 = i;
			}
			
			if(oneGroup.contains(column2)) {
				flag2 = 1;
				whichGroup2 = i;
			}
			
		}
		
		//groupInfo has no two columns. they become a group
		if(flag1 == 0 && flag2 == 0) {
			Set<Integer> oneGroup = new HashSet<Integer>();
			oneGroup.add(column1);
			oneGroup.add(column2);
			int workload = colDistiNum.get(column1) + colDistiNum.get(column2);
			
			if(workload > upperLimit) 
				return (whether = false);
			
			Pair<Set<Integer>, Integer> oneGroupInfo = new Pair<Set<Integer>, Integer>(oneGroup, workload);
			groupInfo.add(oneGroupInfo);
		}
		
		//groupInfo has only one of them. add the one to the group
		if((flag1 + flag2) == 1) {
			
			int whichGroup = whichGroup1 + whichGroup2;
			Set<Integer> oneGroup = groupInfo.get(whichGroup).first_;
			int workload = groupInfo.get(whichGroup).second_;
			
			int column = 0;
			if(flag1 == 0) column = column1;
			if(flag2 == 0) column = column2;
			
			workload += colDistiNum.get(column);
			
			if(workload > upperLimit) 
				return (whether = false);
			
			Set<Integer> newGroup = new HashSet<Integer>();
			newGroup.addAll(oneGroup);
			newGroup.add(column);
			
			if(newGroup.size() > numInGroup) {
				return (whether = false);
			}
			
			Pair<Set<Integer>, Integer> newGroupInfo = new Pair<Set<Integer>, Integer>(newGroup, workload);
			
			groupInfo.remove(whichGroup);
			groupInfo.add(newGroupInfo);
		}
		
		//groupInfo has these two columns. 1. two columns in one group. 2.two columns in two groups--concate the two groups
		if((flag1 + flag2) == 2) {
			
			if(whichGroup1 == whichGroup2) {
				
				return (whether = true);
			}
			else {
				
				int workload = groupInfo.get(whichGroup1).second_ + groupInfo.get(whichGroup2).second_;
				
				if(workload > upperLimit) 
					return (whether = false);
				
				Set<Integer> oneGroup1 = groupInfo.get(whichGroup1).first_;
				Set<Integer> oneGroup2 = groupInfo.get(whichGroup2).first_;
				
				Set<Integer> newGroup = new HashSet<Integer>();
				newGroup.addAll(oneGroup1);
				newGroup.addAll(oneGroup2);
				
				if(newGroup.size() > numInGroup) {
					return (whether = false);
				}
				
				Pair<Set<Integer>, Integer> newGroupInfo = new Pair<Set<Integer>, Integer>(newGroup, workload);
				
				if(groupInfo.contains(whichGroup1))
					groupInfo.remove(whichGroup1);
				
				if(groupInfo.contains(whichGroup2))
					groupInfo.remove(whichGroup2);
				
				groupInfo.add(newGroupInfo);
			}
		}
		 
		
		
		this.groupInfo = groupInfo;
		return (whether = true);
	}

	private int[] drop(int column, 
			HashMap<Pair<Integer, Integer>, Integer> edgePosition, 
			ArrayList<Integer> currentNeighbourList,
			int[] edgeFlag) {
		
		ArrayList<Integer> deleteList = new ArrayList<Integer>();
		ArrayList<Integer> neighbours = recordEquation.get(column);
		
		for(int n = 0; n < neighbours.size(); n++) {
			
			int neighbour = neighbours.get(n);
			int isINcurrent = 0;
			
			for(int m = 0; m < currentNeighbourList.size(); m++) {
				
				int currentNeighbour = currentNeighbourList.get(m);
				if(neighbour == currentNeighbour){
					isINcurrent = 1;
					break;
				}
			}
			
			//not belong to the currentNeighbours
			if(isINcurrent == 0) {
				//put into the deleteLsit so that recordEquation to delete
				deleteList.add(neighbour);
				
				//flag in edgeFlag to tell me the edge is failed when it is 1
				Pair deleteEdge = new Pair();
				if(column <= neighbour)
					deleteEdge = new Pair(column, neighbour);
				else 
					deleteEdge = new Pair(neighbour, column);
				
				int thisPosition = edgePosition.get(deleteEdge);
				edgeFlag[thisPosition] = 1;
			}
			
		}// every neighbour in adjent table
		
		//begin to delete in recordEquation
		recordEquation = delete(recordEquation, deleteList, column);
		
		return edgeFlag;
	}
	
	/**
	 * delete column's neighbours in deleteList
	 * @param recordEquation
	 * @param deleteList 
	 * @param column
	 * @return
	 */
	private HashMap<Integer, ArrayList<Integer>> delete(HashMap<Integer, ArrayList<Integer>> recordEquation, 
														ArrayList<Integer> deleteList, 
														int column) {
		
		ArrayList<Integer> neighbours = recordEquation.get(column);
		neighbours.removeAll(deleteList);
		recordEquation.put(column, neighbours);
		
		//delete in column's neighbours and delete column in those neighbours
		for(int i = 0; i < deleteList.size(); i++) {
			int neighbourColumn = deleteList.get(i);
			ArrayList<Integer> neighbours1 = recordEquation.get(neighbourColumn);
			
			Set<Integer> columnCollector = new HashSet<Integer>();
			columnCollector.add(column);
			
			neighbours1.removeAll(columnCollector);
			recordEquation.put(neighbourColumn, neighbours1);
		}
		
		return recordEquation;
	}
	
	private void setCombineDataSet() {
		
		Set<Integer> columnSet = recordEquation.keySet();
		
		for(Iterator<Integer> ite = columnSet.iterator(); ite.hasNext();) {
			
			int currentColumn = ite.next();
			ArrayList<Integer> pairArray = recordEquation.get(currentColumn);
			//System.out.println("column: " + currentColumn + " pairArray: " + pairArray);
			if(pairArray.size() == 0) uncandidate.add(currentColumn);
			else{
				
				for(int k = 0; k < pairArray.size(); k++){
					
					Pair<Integer, Integer> combinePair = new Pair<Integer, Integer>(0, 0);
					int ToColumn = pairArray.get(k);
					
					if(currentColumn < ToColumn) combinePair = new Pair<Integer, Integer>(currentColumn, ToColumn);
					else combinePair = new Pair<Integer, Integer>(ToColumn, currentColumn);
					
					if( !combinedData.contains(combinePair) ) combinedData.add(combinePair);
					
				}
				
			}
				
		}
		
		keptRelation = combinedData.size();
	}
	
	public void getRetent() {
		String outString = "number of all relations is " + allRelation + " number of kept relations is " + keptRelation;
		System.out.println(outString);
		System.out.println();
	}
	
	//-------------------------------------------Sort---------------------------------------
	
	public ArrayList<Pair<Pair<Integer, Integer>, Double>> sort(ArrayList<Pair<Pair<Integer, Integer>, Double>> edgeInfoList) {
		
		return quickSort(0, edgeInfoList.size() - 1, edgeInfoList);
	}
	
	private ArrayList<Pair<Pair<Integer, Integer>, Double>> quickSort(int low, int high, 
			ArrayList<Pair<Pair<Integer, Integer>, Double>> edgeInfoList) {
		
		if(low < high)
        {

            int result = partition(edgeInfoList, low, high);

            quickSort(low, result - 1, edgeInfoList);

            quickSort(result + 1, high, edgeInfoList);

        }
		
		return edgeInfoList;
	}
	
	private int partition(ArrayList<Pair<Pair<Integer, Integer>, Double>> edgeInfoList, int low,int high)
    {

		Pair<Pair<Integer, Integer>, Double> key = edgeInfoList.get(low); 

        while(low < high)
        {

            while(low < high && edgeInfoList.get(high).second_ >= key.second_) {
            	high--;
            }

            edgeInfoList.set(low, edgeInfoList.get(high));

            while(low < high && edgeInfoList.get(low).second_ <= key.second_) {
            	low++;
            }

            edgeInfoList.set(high, edgeInfoList.get(low));

        }

        edgeInfoList.set(low, key);

        return low;

    }
	
	public void clear() {
		firstMargiDistr.clear();
		secondMargiDistr.clear();
		mutualInfoDistri.clear();
		mutualInfo.clear();
		jointDistr.clear();
		numericalSet.clear();
	}
	
	public Set<Pair<Integer, Integer>> getCombineDataSet() {
		return combinedData;
	}

	public Set<Integer> getSingleColumnSet() {
		
		return uncandidate;
	}

	public long getRows() {
		return Rows;
	}

	public int getCols() {
		return cols;
	}

}
